package org.example.queue;

import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LevelOrder {
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    /**
     * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
     *
     * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        if(root == null) return new ArrayList();
        Queue<Node> queue = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList();
        queue.add(root);
        int count = 0;

        while(!queue.isEmpty()){
            //记录每层节点数
            count = queue.size();
            //出队count次，并且把下一层节点加入队列中
            List<Integer> list = new ArrayList<>();
            while(count--!=0){
                Node cur = queue.remove();
                //将子节点加入队列
                if(cur.children!=null){
                    for(Node node : cur.children){
                        queue.add(node);
                    }
                }
                list.add(cur.val);
            }
            ret.add(list);
        }
        return ret;
    }
}

